package com.shm.leetcode;

/**
 * 419. 甲板上的战舰
 * 给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。
 *
 * 战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
 * 输出：2
 * 示例 2：
 *
 * 输入：board = [["."]]
 * 输出：0
 *
 *
 * 提示：
 *
 * m == board.length
 * n == board[i].length
 * 1 <= m, n <= 200
 * board[i][j] 是 '.' 或 'X'
 *
 *
 * 进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？
 * @author SHM
 */
public class CountBattleships {
    /**
     * 方法一：遍历扫描
     * 题目要求找到矩阵中战舰的数量，战舰用 \texttt{'X'}’X’ 表示，空位用 \texttt{'.'}’.’，而矩阵中的战舰的满足以下两个条件：
     *
     * 战舰只能水平或者垂直放置。战舰只能由子矩阵 1 \times N1×N（11 行，NN 列）组成，或者子矩阵 N \times 1N×1（NN 行, 11 列）组成，其中 NN 可以是任意大小。
     * 两艘战舰之间至少有一个水平或垂直的空位分隔，没有相邻的战舰。
     * 我们遍历矩阵中的每个位置 (i,j)(i,j) 且满足 \textit{board}[i][j] = \texttt{'X'}board[i][j]=’X’，并将以 (i,j)(i,j) 为起点的战舰的所有位置均设置为空位，从而我们即可统计出所有可能的战舰。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(m \times n \times \max(m,n))O(m×n×max(m,n))，其中 mm 是矩阵的行数，nn 是矩阵的列数，我们对于矩阵的每个位置都会遍历一遍以该位置所在的行和列。
     *
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/battleships-in-a-board/solution/jia-ban-shang-de-zhan-jian-by-leetcode-s-kxpc/
     * @param board
     * @return
     */
    public int countBattleships(char[][] board) {
        int m = board.length,n = board[0].length;
//        boolean[][] visited = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j]=='X'){
                    board[i][j]='.';
                    for (int k = j+1; k < n&&board[i][k]=='X'; k++) {
                        board[i][k]='.';
                    }
                    for (int k = i+1; k < m&&board[k][j]=='X'; k++) {
                        board[k][j]='.';
                    }
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 方法二：枚举起点
     * 题目进阶要求一次扫描算法，只使用 O(1)O(1) 额外空间，并且不修改甲板的值。因为题目中给定的两艘战舰之间至少有一个水平或垂直的空位分隔，任意两个战舰之间是不相邻的，因此我们可以通过枚举每个战舰的左上顶点即可统计战舰的个数。假设矩阵的行数为 \textit{row}row，矩阵的列数 \textit{col}col，矩阵中的位置 (i, j)(i,j) 为战舰的左上顶点，需满足以下条件：
     *
     * 满足当前位置所在的值 \textit{board}[i][j] = \texttt{'X'}board[i][j]=’X’；
     * 满足当前位置的左则为空位，即\textit{board}[i][j-1] = \texttt{'.'}board[i][j−1]=’.’；
     * 满足当前位置的上方为空位，即\textit{board}[i-1][j] = \texttt{'.'}board[i−1][j]=’.’；
     * 我们统计出所有战舰的左上顶点的个数即为所有战舰的个数。
     * 复杂度分析
     *
     * 时间复杂度：O(m \times n)O(m×n)，其中 mm 是矩阵的行数，nn 是矩阵的列数，我们只需要遍历一遍矩阵中每个位置即可。
     *
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/battleships-in-a-board/solution/jia-ban-shang-de-zhan-jian-by-leetcode-s-kxpc/
     * @param board
     * @return
     */
    public int countBattleships_1(char[][] board) {
        int m = board.length, n = board[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j]=='X'){
                    if (i>0&&board[i-1][j]=='X'){
                        continue;
                    }
                    if (j>0&&board[i][j-1]=='X'){
                        continue;
                    }
                    ans++;
                }
            }
        }
        return ans;
    }
}
